template<class K, class V>
struct BSTreeNode
{
    BSTreeNode* lchild_; 
    BSTreeNode* rchild_; 
    K key_;              
    V value_;            

    BSTreeNode(const K& key, const V& value) 
        :lchild_(NULL)
        ,rchild_(NULL)
        ,key_(key)
        ,value_(value)
    {}

};



template<class K,class V>
class BSTree
{
    typedef BSTreeNode<K, V> Node;

public:
    BSTree()
        :root_(NULL)
    {}

    
    Node* Find(const K& key)
    {
        return Find_(root_, key);
    }

    Node* Find_(Node* root, const K& key)
    {
        if (root == NULL)
        {
            return NULL;
        }

        if (root->key_ > key) 
        {
            return Find_(root->lchild_, key);
        }
        else if (root->key_ < key)
        {
            return Find_(root->rchild_, key);
        }
        else
        {
            return root;
        }
    }



    
    bool Insert(const K& key, const V& value)
    {
        return Insert_(root_, key, value);
    }

    bool Insert_(Node*& root, const K& key, const V& value)
    {
        if (root == NULL)
        {
            root = new Node(key, value);
            return true;
        }

        if (root->key_ > key)
        {
            return Insert_(root->lchild_, key, value);
        }
        else if(root->key_ < key)
        {
            return Insert_(root->rchild_, key, value);
        }
        else
        {
            return false;
        }
    }



    
    bool Remove(const K& key)
    {
        return Remove_(root_, key);
    }

    bool Remove_(Node*& root, const K& key)
    {
        
        if (root == NULL)
        {
            return false;
        }
        
        if (root->lchild_ == NULL&&root->rchild_ == NULL)
        {
            if (root->key_ == key)
            {
                delete root;
                root = NULL;
                return true;
            }
            else
            {
                return false;
            }

        }


        if (root->key_ > key)
        {
            Remove_(root->lchild_, key);
        }
        else if (root->key_ < key)
        {
            Remove_(root->rchild_, key);
        }
        else
        {
            Node* del = NULL;

            if (root->lchild_ == NULL)      
            {
                del = root;
                root = root->rchild_;
                delete del;
                del = NULL;
                return true;
            }
            else if (root->rchild_ == NULL) 
            {
                del = root;
                root = root->lchild_;
                delete del;
                del = NULL;
                return true;
            }
            else
            {
                Node* RightFirst = root->rchild_;
                
                while (RightFirst->lchild_)
                {
                    RightFirst = RightFirst->lchild_;
                }

                
                swap(root->key_, RightFirst->key_);
                swap(root->value_, RightFirst->value_);


                Remove_(root->rchild_, key);
                return true;
            }
        }
    }


    
    void Output()
    {
        Output_(root_);
        cout << endl;
    }

    void Output_(Node* root)
    {
        if (root == NULL)
        {
            return;
        }

        Output_(root->lchild_);
        cout << root->key_ << " ";
        Output_(root->rchild_);
    }


    Node * self()
    {
        return root_;
    }

private:
    Node* root_;
};

